package com.wdc.回溯;

import com.wdc.queue.Arr;

import java.util.*;

@SuppressWarnings("all")
public class E12Leetcode47 {
    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    private boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        permutetacking2(nums,used);
        return result;
    }

    void permutetacking(int[] nums , boolean[] used){
        if (path.size() == nums.length){
            if (!result.contains(path)){
                result.add(new ArrayList<>(path));

            }
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            permutetacking(nums,used);
            path.removeLast();
            used[i] = false;
        }


    }
    void permutetacking2(int[] nums , boolean[] used){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]){
                continue;
            }
            if (i > 0 && nums[i] == nums[i -1] && used[i -1]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            permutetacking(nums,used);
            path.removeLast();
            used[i] = false;
        }


    }

    public static void main(String[] args) {
        int[] nums = {1,1,2};
        E12Leetcode47 e12Leetcode47 = new E12Leetcode47();
        System.out.println(e12Leetcode47.permuteUnique(nums));
    }
}
